package cyc2018.分治;

import java.util.ArrayList;
import java.util.List;

/**
 * todo 为运算表达式设计优先级
 */
public class Test241 {

    public static List<Integer> diffWaysToCompute(String input) {
        List<Integer> ways = new ArrayList<>();
        // 分割原理：每次遇到一个操作符的时候，就以该操作符左边的全部元素为一部分，右边的全部元素为一部分，计算两部分的结果
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                // 1. 只取 0~i 的数据作为左半部分的集合
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                // 2. 取 i+1 到最后的元素为右半部分的集合
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                // 3. 然后取出两边的元素求结果
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                ways.add(l + r);
                                break;
                            case '-':
                                ways.add(l - r);
                                break;
                            case '*':
                                ways.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        // 若最后集合里面不存在元素，也就意味着不存在运算符，将将当前字符串变为数字返回即可
        if (ways.size() == 0) {
            ways.add(Integer.valueOf(input));
        }
        return ways;
    }

    public static void main(String[] args) {
        String str = "2-1-1";
        List<Integer> list = diffWaysToCompute(str);
        list.forEach((e) -> System.out.print(e + " "));
    }
}
